package Other;

import java.util.UUID;

public class leet_300 {
    public static void main(String[] args) {


    }

}

class Solution_300 {
    public int lengthOfLIS(int[] nums) {
        return 0;
    }

    /**
     * 动态规划  数组为每一个位置的最长子序列
     * dp数组为每一个索引位置的最大的递增子序列
     * 如果当前下标数字大于前面的数字，就把其最大递增长度比较加1
     * 逐次比较到前一个
     * @param nums
     * @return
     */
    public int dynamicLengthOfLIS(int[] nums){
        if(nums.length==0){return 0;}
        // 数组为每一个位置的最长子序列
        int[] dp = new int[nums.length];
        dp[0] = 1;
        // 最长子序列长度
        int maxLength = 1;
        for(int i=1; i<nums.length; i++){
            int nums1 = nums[i];
            int tmpLength = 1;
            for(int j=0; j<i; j++){
                int nums2 = nums[j];
                if(nums1 > nums2){
                    int tmpLength2 = dp[j]+1 ;
                    tmpLength = Math.max(tmpLength, tmpLength2);
                }
            }
            maxLength = Math.max(tmpLength, maxLength);

            dp[i] = tmpLength;
        }
        return maxLength;
    }

    /**
     * 贪心 :
     *      自己维护一个递增的数组
     *      如果当前位置大于数组的最后一个位置，把该位置加入数组
     *      如果当前位置小于数组的最后一个位置，
     *      找到一个位置其2边的数在二者之间，默认数组下一位是无穷大
     *      最后返回该数组的长度
     * @param nums
     * @return
     */
    public int greedyLengthOfLIS(int[] nums){
        int len = 1, n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] d = new int[n];
        d[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len-1]) {
                // len 的位置填充当前值
                // 并且把len+1 代表长度加1
                d[len] = nums[i];
                len++;
            } else {
                int left = 0;
                int right = len -1;
                int value = nums[i];
                // 找到位置
                while(left<=right){
                    int mid = (left+right)/2;
                    // 如果相同跳出循环
                    if(d[mid] == value){
                        left = mid;
                        break;
                    }
                    // 如果 value大于中间值 说中间值需要往右走 左指针右移
                    if(value > d[mid]){
                        left = mid+1;
                    }else {
                        right = mid -1;
                    }
                }
                d[left] = value;
            }
        }
        return len;
    }


}

